#include <iostream>
#include <vector>
#include <functional>
#include <utility>
#include <cassert>
using namespace std;

// 闭散列/开放地址法
namespace OpenAddressing
{
    // 状态枚举
    enum State
    {
        EMPTY,
        EXIST,
        DELETE
    };

    // 哈希数据元素
    template <class K, class V>
    struct HashData
    {
        pair<K, V> _pair;
        State _state = EMPTY;
    };

    // 哈希表
    template <class K, class V>
    class HashTable
    {
    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0; // 存储的数据个数

    public:
        // 插入函数
        bool Insert(const pair<K, V> &pair)
        {
            // 值已存在 插入错误
            if (Find(pair.first))
                return false;

            // 负载因子/荷载系数 -- Load_Factor = _n / _tables.size();

            //(double)_n / (double)_tables.size() >= 0.7
            //_n * 10 / _tables.size() >= 7

            // 使得扩容发生的条件: size为0 负载因子达到阈值
            if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
            {
                / 低级代码 /
                    /*
                    //先更新size 由size作为参数扩容 解决只改容量 不更新访问范围的问题
                    size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;

                    //调用vector的有参构造[有参构造里调用reserve] 创建一个新表
                    vector<HashData<K,V>> newtables(newsize);

                    //遍历旧表  由哈希函数更新数据位置
                    for (auto& e :  _tables)
                    {
                        if (e._state == EXIST)
                        {
                            //哈希函数计算出的下标
                            size_t hashi = pair.first % newtables.size();

                            //重新线性探测
                            size_t index = hashi;//index代替hashi进行操作 保留原始hashi的值不变
                            for (size_t i = 1; newtables[index]._state == EXIST; ++i)
                            {
                                index = hashi + i;        //从原始下标不断 +1 +2 +3 ...
                                index %= newtables.size();//防止越界 只在表内定位index
                            }

                            //将数据放入合适位置
                            newtables[index]._pair = e._pair;
                            newtables[index]._state = EXIST;
                        }
                    }

                    //新表的数据才是我们想要的数据 交换后 newtables中存放的变为旧数据
                    //newtables是个局部变量 让其"自生自灭"
                    _tables.swap(newtables);
                    */

                    //  高级代码 //
                    size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                HashTable<K, V> other;
                other._tables.resize(newsize);

                for (auto &e : _tables)
                {
                    if (e._state == EXIST)
                        other.Insert(e._pair);
                }

                _tables.swap(other._tables);
                /

                // 以上高级代码实际是对下面的线性探测进行了复用
            }

            // 哈希函数计算出的下标
            size_t hashi = pair.first % _tables.size();

            // 线性探测
            size_t index = hashi; // index代替hashi进行操作 保留原始hashi的值不变
            for (size_t i = 1; _tables[index]._state == EXIST; ++i)
            {
                index = hashi + i;       // 从原始下标不断 +1 +2 +3 ...
                index %= _tables.size(); // 防止越界 只在表内定位index
            }
            // 将数据放入合适位置
            _tables[index]._pair = pair;
            _tables[index]._state = EXIST;
            _n++; // 数据个数++

            return true;
        }

        // 查找函数
        HashData<K, V> *Find(const K &key)
        {
            // 哈希表为空 返回nullptr
            if (_tables.size() == 0)
                return nullptr;

            // 哈希函数计算出的下标
            size_t hashi = key % _tables.size();

            // 线性探测
            size_t index = hashi;
            for (size_t i = 1; _tables[index]._state != EMPTY; ++i)
            {
                // obj是key的前提是obj存在
                if (_tables[index]._state == EXIST && _tables[index]._pair.first == key)
                {
                    return &_tables[index];
                }

                index = hashi + i;
                index %= _tables.size();

                // 当表中元素状态非exist即delete时
                // for循环判断条件一直为真 死循环
                // 解决: 当找了一圈还未找到
                // 表中无此key 返回false
                if (index == hashi)
                    break;
            }
            return nullptr;
        }

        // 删除函数
        bool Erase(const K &key)
        {
            HashData<K, V> *pos = Find(key);
            if (pos)
            {
                pos->_state = DELETE;
                --_n; // 虽然已标记删除 仍然要使数据个数减减 防止有用数据未达到阈值就执行扩容
                return true;
            }
            else
                return false;
        }
    };
    //  测试函数  ///
    void TestHashTable()
    {
        int a[] = {3, 33, 2, 13, 5, 12, 1002};
        HashTable<int, int> ht;
        // 插入
        for (auto &e : a)
            ht.Insert(make_pair(e, e));
        // 插入第8个数据 达到阈值  测试扩容
        ht.Insert(make_pair(15, 15));

        // 查找 + 删除
        int tmp = 12;
        if (ht.Find(tmp))
            cout << tmp << "在" << endl;
        else
            cout << tmp << "不在" << endl;

        ht.Erase(tmp);

        if (ht.Find(tmp))
            cout << tmp << "在" << endl;
        else
            cout << tmp << "不在" << endl;
    }
}

// 开散列/链地址法
namespace ChainAddressing
{
    // 结点类
    template <class K, class V>
    struct HashNode
    {
        HashNode<K, V> *_next;
        pair<K, V> _pair;

        HashNode(const pair<K, V> &pair)
            : _next(nullptr), _pair(pair)
        {
        }
    };

    // 哈希函数类
    template <class K>
    struct hash
    {
        size_t operator()(const K &key)
        {
            return key;
        }
    };
    template <>
    struct hash<string>
    {
        size_t operator()(const string &s)
        {
            size_t value = 0;
            for (auto ch : s)
            {
                value = value * 131 + ch;
            }
            return value;
        }
    };

    struct StringToInt
	{
		size_t operator()(const string& s)
		{
			//问题代码:
			//return s[0];
			//1.如果传空串 违背使用者意愿
			//2.不同单词相同首字母均会哈希冲突 不太合适 

			//代码改进
			size_t value = 0;
			for (auto& ch : s)
			{
				value = value * 131 + ch;
			}
			return value;
		}
	};

    // 哈希表类
    template <class K, class V, class Hash = hash<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;

    private:
        vector<Node *> _tables; // 指针数组
        size_t _n = 0;          // 存储有效数据个数

    public:
        // 析构函数
        ~HashTable()
        {
            for (auto &ptr : _tables)
            {
                while (ptr)
                {
                    // 记录下一个结点
                    Node *next = ptr->_next;
                    // 释放当前结点
                    delete ptr;
                    // 更新ptr
                    ptr = next;
                }

                ptr = nullptr;
            }
        }

        // 查找函数
        Node *Find(const K &key)
        {
            // 为空不查找 返回nullptr
            if (_tables.size() == 0)
                return nullptr;

            // 哈希函数计算的下标
            size_t hashi = key % _tables.size();
            // 首先得到表里的指针 即相当于每一个桶的头指针
            //[实际上 每一个桶就是一个链表 表中的ptr是每一个链表的哨兵指针]
            Node *ptr = _tables[hashi];

            while (ptr)
            {
                if (ptr->_pair.first == key)
                    return ptr;
                ptr = ptr->_next;
            }

            return nullptr;
        }

        // 删除函数
        bool Erase(const K &key)
        {
            // 哈希函数计算的下标
            size_t hashi = key % _tables.size();
            // 首先得到表里的指针 即相当于每一个桶的头指针
            //[实际上 每一个桶就是一个链表 表中的ptr是每一个链表的哨兵指针]
            Node *ptr = _tables[hashi];
            Node *prv = nullptr;

            while (ptr)
            {
                // 当前值为目标值 执行删除操作
                if (ptr->_pair.first == key)
                {
                    if (prv == nullptr)
                        _tables[hashi] = ptr->_next;
                    else
                        prv->_next = ptr->_next;

                    delete ptr;
                    return true;
                }
                // 当前值不为目标值 继续向下遍历
                else
                {
                    prv = ptr;
                    ptr = ptr->_next;
                }
            }
            return false;
        }

        // 插入函数
        bool Insert(const pair<K, V> &pair)
        {
            // 表中已有 返回false
            if (Find(pair.first))
                return false;

            Hash hash;

            // 负载因子/荷载系数 -- Load_Factor = _n / _tables.size();
            // 负载因子 == 1时 扩容+更新数据
            if (_n == _tables.size())
            {
                ///  高级代码1.0  /
                /*
                size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                HashTable<K, V> newht;
                newht.resize(newsize);
                for (auto& ptr : _tables)
                {
                    while (ptr)
                    {
                        newht.Insert(ptr->_pair);
                        ptr = ptr->_next;
                    }
                }

                _tables.swap(newht._tables);
                */

                // 引进stl库素数思想
                // size_t newsize = GetNextPrime(_tables.size());
                size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;

                vector<Node *> newtables(newsize, nullptr);
                // 遍历旧表 取出旧表里每一个指针
                for (auto &ptr : _tables)
                {
                    // ptr是旧表里存储的每一个指针
                    // 它指向当前哈希桶的首结点 即他存储的是首结点的地址
                    while (ptr)
                    {
                        // 算出 当前结点根据新哈希函数计算的新下标
                        size_t hashi = hash(ptr->_pair.first) % newtables.size();

                        // ptr是首结点的地址 ptr->_next为第二个结点的地址
                        Node *next = ptr->_next;

                        // 头插到新表
                        ptr->_next = newtables[hashi];
                        newtables[hashi] = ptr;

                        // 更新ptr 即向下遍历
                        ptr = next;
                    }
                }

                _tables.swap(newtables);
            }

            // 哈希函数计算出的下标
            size_t hashi = hash(pair.first) % _tables.size();
            // 链表头插
            Node *newnode = new Node(pair);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;

            return true;
        }

        // 最大桶数据个数
        size_t MaxBucketSize()
        {
            size_t max = 0;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                auto ptr = _tables[i];
                size_t size = 0;
                while (ptr)
                {
                    ++size;
                    ptr = ptr->_next;
                }

                // 每个桶数据个数
                // printf("[%d] -> %d\n", i, size);

                if (size > max)
                    max = size;
            }
            return max;
        }

        size_t GetNextPrime(size_t index)
        {
            static const int num = 28;
            static const unsigned long prime[num] = {
                53, 97, 193, 389, 769,
                1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433,
                1572869, 3145739, 6291469, 12582917, 25165843,
                50331653, 100663319, 201326611, 402653189, 805306457,
                1610612741, 3221225473, 4294967291};

            size_t i = 0;
            for (i = 0; i < num; ++i)
            {
                if (prime[i] > index)
                    return prime[i];
            }

            return prime[i];
        }
    };

    // 测试函数
    void TestHashTable1()
    {
        int a[] = {3, 33, 2, 13, 5, 12, 1002};
        HashTable<int, int> ht;
        for (auto &e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Insert(make_pair(15, 15));
        ht.Insert(make_pair(25, 25));
        ht.Insert(make_pair(35, 35));
        ht.Insert(make_pair(45, 45));
    }

    void TestHashTable2()
    {
        int a[] = {3, 33, 2, 13, 5, 12, 1002};
        HashTable<int, int> ht;
        for (auto &e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Erase(12);
        ht.Erase(3);
        ht.Erase(33);
    }

    // 字符串问题
    void TestHashTable3()
    {
        // 不实现类模板特化 显示传StringToInt
        // HashTable<string, string, StringToInt> ht;
        // 使用类模板特化 不需要显示传 更符合大佬设计的底层哈希
        HashTable<string, string> ht;
        ht.Insert(make_pair("Kevin", "凯文"));
        ht.Insert(make_pair("Eddie", "彭于晏"));
        ht.Insert(make_pair("Tom", "汤姆"));
        ht.Insert(make_pair("Jerry", "杰瑞"));
        ht.Insert(make_pair("", "null_string"));
    }

    // 性能测试
    void TestHashTable4()
    {
        size_t N = 900000;
        HashTable<int, int> ht;
        srand(time(0));
        for (size_t i = 0; i < N; ++i)
        {
            size_t x = rand() + i;
            ht.Insert(make_pair(x, x));
        }

        cout << "最大桶数据个数" << ht.MaxBucketSize() << endl;
    }
}
